﻿#include "test.h"

//给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
//
//选择二叉树中 任意 节点和一个方向（左或者右）。
//如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
//改变前进方向：左变右或者右变左。
//重复第二步和第三步，直到你在树中无法继续移动。
//交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
//
//请你返回给定树中最长 交错路径 的长度。

//合并了原有的 _longestZigZag 和 dfs 函数，避免重复递归调用
//使用引用参数 maxLen 记录最长路径，不需要额外的返回值来传递这个信息
//在每次递归中，不仅继续当前的 zigzag 路径，还考虑从当前节点重新开始的情况
//时间复杂度从 O(n²) 优化到 O(n)，其中 n 是树中节点的数量
class Solution {
    int maxAns = 0;
public:
    int longestZigZag(TreeNode* root)
    {
        if (!root)   return 0;
        dfs(root, 0, 0);
        dfs(root, 1, 0);
        return maxAns;
    }
private:
    //len代表当前的有效长度！
    void dfs(TreeNode* root, bool flag, int len) //规定flag为0向左，flag为1向右
    {
        if (!root)
            return;
        maxAns = max(maxAns, len);
        //后续遍历
        if (flag == 0) //当前层向左
        {
            if (root->left) dfs(root->left, 1, len + 1); // 向左之后向右
            if (root->right) dfs(root->right, 0, 1);
        }
        else
        {
            if (root->left) dfs(root->left, 1, 1);
            if (root->right) dfs(root->right, 0, len + 1);
        }

    }
};


// 超时写法：仿照一个root有效，一个root无效的思路
// 递归层次太深，会超时。时间复杂度为O(N^2)
class Solution {
public:
    int longestZigZag(TreeNode* root)
    {
        return _longestZigZag(root) - 1;
    }
private:
    int _longestZigZag(TreeNode* root)
    {
        if (!root)
            return 0;
        int ret = max(dfs(root, 0), dfs(root, 1));
        int left = 0, right = 0;
        if (root->left)
            left = _longestZigZag(root->left);
        if (root->right)
            right = _longestZigZag(root->right);

        return max(ret, left > right ? left : right);
    }
    //root有效的长度
    int dfs(TreeNode* root, bool flag) //规定flag为0向左，flag为1向右
    {
        if (!root)
            return 0;

        int ret = 0;
        //后续遍历
        if (flag == 0) //如果这一层是向左走
        {
            //下一层向右走 1
            if (root->left)
                ret = dfs(root->left, 1);
        }
        else //如果这一层向右走
        {
            //下一层向左走 0
            if (root->right)
                ret = dfs(root->right, 0);
        }
        return 1 + ret;
    }
};